#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

/*
1 2 7 5
2 1 8
3 4 5 6
4 6 3
5 1 3
6 7 3 4
7 1 8 6
8 2 7
*/

struct edge_node
{
	bool visited;
	int vertex_num;
	struct edge_node* next;
};

template<class T> class mtree_node
{
	public:
		mtree_node() :parent(NULL),format("  ") {}
		mtree_node(const T& x) :name(x), parent(NULL), format("  ") {}

		~mtree_node() {}

		T name;
		//默认为两个空格  
		string format;

		mtree_node* parent;
		vector<mtree_node*> children;
};

vector <struct edge_node> vertex(8);

int init_vector ()
{
	for (int i = 0; i < 8; i++)
	{
		vertex[i].visited = false;
		vertex[i].vertex_num = i + 1;
		vertex[i].next = NULL;
	}
	return 0;
}

int make_adj_table_from_adj_matrix (int adj_matrix[][8])
{
	struct edge_node* curr_node = NULL;
	for (int i = 0; i < 8; i++ )
	{
		curr_node = &vertex[i];
		for (int j = 0; j < 8; j++ )
		{
			if ( *(*(adj_matrix+i)+j) > 0)
			{
				curr_node->next = new struct edge_node;
				curr_node->next->visited = false;
				curr_node->next->vertex_num = j + 1;
				curr_node->next->next = NULL;
				curr_node = curr_node->next;
			}
		}
	}
	return 0;
}

int destroy_adj_table ()
{
	struct edge_node* curr_node;
	struct edge_node* temp;
	for (int i = 0; i < vertex.size(); i++)
	{
		curr_node = vertex[i].next;
		vertex[i].next = NULL;
		while (curr_node != NULL)
		{
			temp = curr_node;
			curr_node = curr_node->next;
			delete temp;
		}
	}
	return 0;
}

int print_adj_table ()
{
	struct edge_node* curr_node = NULL;
	for (int i = 0; i < vertex.size(); i++)
	{
		curr_node = &vertex[i];
		while ( NULL != curr_node )
		{
			cout << curr_node->vertex_num << " ";
			curr_node = curr_node->next;
		}
		cout << endl;
	}
}

int set_all_visited (int const vertex_num)
{
	struct edge_node* curr_node = NULL;
	for (int i = 0; i < vertex.size(); i++)
	{
		curr_node = &vertex[i];
		while ( NULL != curr_node )
		{
			if ( vertex_num == curr_node->vertex_num )
			{
				curr_node->visited = true;
			}
			curr_node = curr_node->next;
		}
	}
	return 0;
}

int tree_search ()
{
	return 0;
}

int make_tree_form_adj_table_by_bfs ()
{
	mtree_node<int>* root = NULL;
	mtree_node<int>* parent = NULL;
	mtree_node<int>* temp = NULL;
	//mtree_node<int>* curr_tree_node = NULL;
	struct edge_node* curr_node = NULL;
	queue<int> que;
	que.push(vertex[0].vertex_num);
	set_all_visited(que.back());
	root = new mtree_node<int> (que.back());
	parent = root;
	while (!que.empty())
	{
		curr_node = vertex[que.front()-1].next;
		while ( NULL != curr_node )
		{
			if ( !(curr_node->visited) )
			{
				que.push(curr_node->vertex_num);
				set_all_visited(curr_node->vertex_num);
				temp = new mtree_node<int> (que.back());
				parent->children.push_back(temp);
				//父节点的指向要改变
			}
			curr_node = curr_node->next;
		}
		que.pop();
	}

	return 0;
}

int print_tree ()
{
	return 0;
}

int adj_table_traversal_by_bfs ()
{
	queue<int> que;
	que.push(vertex[0].vertex_num);
	set_all_visited(que.back());
	cout << que.back() << endl;
	struct edge_node* curr_node = NULL;
	while (!que.empty())
	{
		curr_node = vertex[que.front()-1].next;
		while ( NULL != curr_node )
		{
			if ( !(curr_node->visited) )
			{
				que.push(curr_node->vertex_num);
				cout << que.back() << " ";
				set_all_visited(curr_node->vertex_num);
			}
			curr_node = curr_node->next;
		}
		que.pop();
		cout << endl;
	}
	return 0;
}

int main (int argc, char* argv[])
{
	int adj_matrix[8][8] = {{0, 1, 0, 0, 1, 0, 1, 0}, 
				{1, 0, 0, 0, 0, 0, 0, 1}, 
				{0, 0, 0, 1, 1, 1, 0, 0}, 
				{0, 0, 1, 0, 0, 1, 0, 0}, 
				{1, 0, 1, 0, 0, 0, 0, 0}, 
				{0, 0, 1, 1, 0, 0, 1, 0}, 
				{1, 0, 0, 0, 0, 1, 0, 1}, 
				{0, 1, 0, 0, 0, 0, 1, 0}};
	init_vector();
	make_adj_table_from_adj_matrix(adj_matrix);
	print_adj_table();
	adj_table_traversal_by_bfs();
	destroy_adj_table();
	print_adj_table();
	return 0;
}


